package com.se.algorithm;

import lombok.extern.log4j.Log4j2;

import java.util.Arrays;

/**
 * @Author: hdu_huang
 * @Date: 2019/1/23 10:20
 *  递归Recurse(尾递归) 是种思想
 * 1.初始值 initial value
 * 2.结束条件 terminate condition
 * 3.算法(公式) algorithm(expression)
 * 递归都能改为迭代
 */

//程序计数器是java虚拟机中唯一一块不会产生error的内存区域  Xss StackOverflowError
@Log4j2
public class RecurseTest {
    public static void main(String[] args) {

        log.info(naturalSequenceSum(100));
        log.info(naturalSequenceSum(100,1));
        log.info(factorial(5));
        log.info(factorial(5,1));

        log.info(fibonacciSequence(10,1, 1)); //89

        int[] arr = {1, 6, 3, 7, 2, 4, 8};

        quickSort(arr,0, arr.length - 1);
        log.info(Arrays.toString(arr));

    }

    // f(n) = f(n-1) + n; => f(1) + ... n-1 + n => n(n+1) / 2
    private static int naturalSequenceSum(int n) {
        if (n == 1) {
            return 1;
        }

        return n + naturalSequenceSum(n - 1); //不是尾递归
    }

    //尾递归相当于 把递归变成迭代了  尾递归可以把初始条件传入
    private static int naturalSequenceSum(int n, int initial) {


        if (n == 1) {
            return initial;
        }

        return naturalSequenceSum(n - 1, n + initial); //尾递归 [Java/Js不进行尾调用优化]
    }

    //Factorial 阶乘  f(n) = n * f(n-1) =>
    private static int factorial(int n) {
        if (n == 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }

    private static int factorial(int n, int initial) {

        if (n == 1) {
            return initial;
        }

        return factorial(n - 1, n * initial);
    }

    private static int fibonacciSequence(int n, int initial1, int initial2) {
        if (n <= 0) return -1;
        if (n == 1) return initial2;
        return fibonacciSequence(n - 1, initial2, initial2 + initial1);
    }

    //快速排序
    private static void quickSort(int[] array, int left, int right) {
        int l = left;
        int r = right;
        int point = array[(left + right) / 2];

        while (l < r) {
            while (array[l] < point) {
                l++;
            }
            while (array[r] > point) {
                r--;
            }
            //退出循环
            if (l >= r) break;

            //交换两个数
            array[r] = array[r] ^ array[l];
            array[l] = array[r] ^ array[l];
            array[r] = array[r] ^ array[l];

            if (array[l] == point) r--;
            if (array[r] == point) l++;

            if (l == r) {
                l++;
                r--;
            }

            if (left < r) quickSort(array, left, r);
            if (right > l) quickSort(array, l, right);
        }
    }
}
